package PrefixSum$DoublePointer;

/**
 * 二维区域和检索，矩阵不可变
 * https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
 * 前缀和数组 S[i][j] = S[i-1][j] + S[i][j-1] +S[i-1][j-1] + A[i][j]
 * 子矩阵和(p, q)为左上角,(i, j)为右下角，sum(p,q,i,j) = S[i][j] - S[i][q-1] - S[p-1][j] + A[p-1][q-1]
 */
public class RangeSumQuery {
    int[][] SMatrix;
    public void NumMatrix(int[][] matrix) {
        SMatrix = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 1; i <= matrix.length; i++){
            for (int j = 1; j <= matrix[0].length; j++){
                SMatrix[i][j] = SMatrix[i - 1][j] + SMatrix[i][j - 1] + SMatrix[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        row1++;
        col1++;
        row2++;
        col2++;
        return SMatrix[row2][col2] - SMatrix[row2][col1 - 1] - SMatrix[row1 - 1][col2] + SMatrix[row1 - 1][col1 - 1];
    }
}
